package com.practice.recursive;

import java.util.ArrayList;

public class HeapSequence {
	public int count(int N) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i=0; i<N; i++) list.add(i);
		return permute(new ArrayList<Integer>(), list);
	}
	
	private int permute(ArrayList<Integer> s, ArrayList<Integer> pool) {
		int count = 0;
		if (pool.size() == 0) {
			return 1;
		}

		int N = pool.size();
		for (int i=0; i<N; i++) {
			int t = pool.get(i);
			if (s.size()==0 || s.get((s.size()-1)/2) < t) {
				s.add(pool.remove(i));
				count += permute(s, pool);
				pool.add(i, s.remove(s.size() - 1));
			}
		}
		
		return count;
	}
	
	public static void main(String[] args) {
		HeapSequence hs = new HeapSequence();
		for (int i=1; i<15; i++) System.out.print(hs.count(i) + " ");
		System.out.println();
	}
}
